#pragma once

#include <thread>
#include <mutex>
#include <shared_mutex>
#include <condition_variable>
#include <future>
#include <latch>
#include <barrier>
#include <atomic>
#include <memory>
#include <cassert>
#include <array>
#include <cstdint>
#include <vector>
#include <queue>


namespace hello
{

/**
 * concurrent queue implemented by std::queue
 */
template<typename T>
class scqueue
{
public:
    scqueue(size_t _cap = SIZE_MAX) : _capacity(_cap) { }

    scqueue(const scqueue&) = delete;
    scqueue& operator = (const scqueue&) = delete;

    scqueue(scqueue&&) noexcept = delete;
    scqueue& operator = (scqueue&&) noexcept = delete;

public:
    void push(const T& x)
    {
        std::unique_lock<std::mutex> ul(_mt);
        _cv.wait(ul, [this](){ return _que.size() < _capacity; });
        _que.push(x);
        ul.unlock();
        _cv.notify_one();
    }

    bool try_push(const T& x)
    {
        std::unique_lock<std::mutex> ul(_mt);
        if (_que.size() >= _capacity) return false;
        _que.push(x);
        return true;
    }

    T poll()
    {
        std::unique_lock<std::mutex> ul(_mt);
        _cv.wait(ul, [this](){ return _que.size() > 0; });
        T tmp = std::move(_que.front());
        _que.pop();
        ul.unlock();
        _cv.notify_one();
        return std::move(tmp);
    }

    std::pair<bool, T> try_poll()
    {
        std::unique_lock<std::mutex> ul(_mt);
        if (_que.size() <= 0)
        {
            return { false, {} };
        }
        T tmp = std::move(_que.front());
        _que.pop();
        ul.unlock();
        return { true, std::move(tmp) };
    }

    inline size_t size()
    {
        return _que.size();
    }

    inline bool empty()
    {
        return _que.size() == 0;
    }

    inline size_t capacity()
    {
        return _capacity;
    }

private:
    size_t _capacity;
    std::queue<T> _que;
    std::mutex _mt;
    std::condition_variable _cv;

};


/**
 * lock-free queue implemented by std::queue
 */
template<typename T>
class suqueue
{
public:
    suqueue(size_t _cap = SIZE_MAX) : _capacity(_cap) { }

    suqueue(const suqueue&) = delete;
    suqueue& operator = (const suqueue&) = delete;

    suqueue(suqueue&&) noexcept = delete;
    suqueue& operator = (suqueue&&) noexcept = delete;

public:
    void push(const T& x)
    {
        while (1)
        {
            while (_flag.test_and_set()) ;

            if (_que.size() >= _capacity)
                _flag.clear();
            else
                break;
        }
        _que.push(x);
        _flag.clear();
    }

    bool try_push(const T& x)
    {
        while (_flag.test_and_set()) ;
        if (_que.size() >= _capacity)
        {
            _flag.clear();
            return false;
        }
        _que.push(x);
        _flag.clear();
        return true;
    }

    T poll()
    {
        while (1)
        {
            while (_flag.test_and_set()) ;

            if (_que.size() <= 0)
                _flag.clear();
            else
                break;
        }
        T tmp = _que.front();
        _que.pop();
        _flag.clear();
        return std::move(tmp);
    }

    std::pair<bool, T> try_poll()
    {
        while (_flag.test_and_set()) ;
        if (_que.size() <= 0)
        {
            _flag.clear();
            return { false, {} };
        }
        T tmp = _que.front();
        _que.pop();
        _flag.clear();
        return { true, std::move(tmp) };
    }

    inline size_t size()
    {
        
        return _que.size();
    }

    inline bool empty()
    {
        return _que.size() == 0;
    }

    inline size_t capacity()
    {
        return _capacity;
    }

private:
    size_t _capacity;
    std::queue<T> _que;
    std::atomic_flag _flag;

};


/**
 * concurrent queue implemented by node-list
 */
template<typename T>
class hcqueue
{
private:
    struct node
    {
        T val;
        node *next;
        node(T _v) :
            val(std::move(_v)),
            next(nullptr)
        {
        }
    };

private:
    inline void destroy()
    {
        std::lock_guard<std::mutex> lg(_mt);
        node* tmp = _head;
        while (tmp)
        {
            node* td = tmp;
            tmp = tmp->next;
            delete td;
        }
        _head = _tail = nullptr;
        _size = 0;
    }

public:
    ~hcqueue()
    {
        destroy();
    }

public:
    hcqueue(size_t _cap = SIZE_MAX) :
        _capacity(_cap),
        _size(0),
        _head(nullptr),
        _tail(nullptr)
    {
        _head = _tail = new node({});
    }

    hcqueue(const hcqueue&) = delete;
    hcqueue& operator = (const hcqueue&) = delete;

    hcqueue(hcqueue&&) noexcept = delete;
    hcqueue& operator = (hcqueue&&) noexcept = delete;

public:
    void push(const T& x)
    {
        auto ta = new node(x);
        std::unique_lock<std::mutex> ul(_mt);
        _cv.wait(ul, [this](){ return _size < _capacity; });
        _tail->next = ta;
        _tail = ta;
        ++_size;
        ul.unlock();
        _cv.notify_one();
    }

    bool try_push(const T& x)
    {
        std::unique_lock<std::mutex> ul(_mt);
        if (_size >= _capacity) return false;
        auto ta = new node(x);
        _tail->next = ta;
        _tail = ta;
        ++_size;
        return true;
    }

    T poll()
    {
        std::unique_lock<std::mutex> ul(_mt);
        _cv.wait(ul, [this](){ return _size > 0; });
        auto td = _head->next;
        _head->next = td->next;
        if (!_head->next) _tail = _head;
        --_size;
        ul.unlock();
        _cv.notify_one();
        T tmp = std::move(td->val);
        delete td;
        return std::move(tmp);
    }

    std::pair<bool, T> try_poll()
    {
        std::unique_lock<std::mutex> ul(_mt);
        if (_size <= 0) return { false, {} };
        auto td = _head->next;
        _head->next = td->next;
        if (!_head->next) _tail = _head;
        --_size;
        ul.unlock();
        T tmp = std::move(td->val);
        delete td;
        return { true, std::move(tmp) };
    }

    inline size_t size()
    {
        return _size;
    }

    inline bool empty()
    {
        return _size == 0;
    }

    inline size_t capacity()
    {
        return _capacity;
    }

private:
    size_t _capacity;
    size_t _size;
    node *_head;
    node *_tail;
    std::mutex _mt;
    std::condition_variable _cv;

};


/**
 * lock-free queue implemented by node-list
 */
template<typename T>
class huqueue
{
private:
    struct node
    {
        T val;
        node *next;
        node(T _v) :
            val(std::move(_v)),
            next(nullptr)
        {
        }
    };

private:
    inline void destroy()
    {
        while (_flag.test_and_set()) ;
        node* tmp = _head;
        while (tmp)
        {
            node* td = tmp;
            tmp = tmp->next;
            delete td;
        }
        _head = _tail = nullptr;
        _size = 0;
        _flag.clear();
    }

public:
    ~huqueue()
    {
        destroy();
    }

public:
    huqueue(size_t _cap = SIZE_MAX) :
        _capacity(_cap),
        _size(0),
        _head(nullptr),
        _tail(nullptr)
    {
        _head = _tail = new node({});
    }

    huqueue(const huqueue&) = delete;
    huqueue& operator = (const huqueue&) = delete;

    huqueue(huqueue&&) noexcept = delete;
    huqueue& operator = (huqueue&&) noexcept = delete;

public:
    void push(const T& x)
    {
        auto ta = new node(x);
        while (1)
        {
            while (_flag.test_and_set()) ;

            if (_size >= _capacity)
                _flag.clear();
            else
                break;
        }
        _tail->next = ta;
        _tail = ta;
        ++_size;
        _flag.clear();
    }

    bool try_push(const T& x)
    {
        while (_flag.test_and_set()) ;
        if (_size >= _capacity)
        {
            _flag.clear();
            return false;
        }
        auto ta = new node(x);
        _tail->next = ta;
        _tail = ta;
        ++_size;
        _flag.clear();
        return true;
    }

    T poll()
    {
        while (1)
        {
            while (_flag.test_and_set()) ;

            if (_size <= 0)
                _flag.clear();
            else
                break;
        }
        auto td = _head->next;
        _head->next = td->next;
        if (!_head->next) _tail = _head;
        --_size;
        _flag.clear();
        T tmp = std::move(td->val);
        delete td;
        return std::move(tmp);
    }

    std::pair<bool, T> try_poll()
    {
        while (_flag.test_and_set()) ;
        if (_size <= 0)
        {
            _flag.clear();
            return { false, {} };
        }
        auto td = _head->next;
        _head->next = td->next;
        if (!_head->next) _tail = _head;
        --_size;
        _flag.clear();
        T tmp = std::move(td->val);
        delete td;
        return { true, std::move(tmp) };
    }

    inline size_t size()
    {
        return _size;
    }

    inline bool empty()
    {
        return _size == 0;
    }

    inline size_t capacity()
    {
        return _capacity;
    }

private:
    size_t _capacity;
    size_t _size;
    node *_head;
    node *_tail;
    std::atomic_flag _flag;

};

}
